{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Battleships in a Board"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countBattleships"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #甲板上的战舰"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个大小为 <code>m x n</code> 的矩阵 <code>board</code> 表示甲板，其中，每个单元格可以是一艘战舰 <code>'X'</code> 或者是一个空位 <code>'.'</code> ，返回在甲板 <code>board</code> 上放置的 <strong>战舰</strong> 的数量。</p>\n",
    "\n",
    "<p><strong>战舰</strong> 只能水平或者垂直放置在 <code>board</code> 上。换句话说，战舰只能按 <code>1 x k</code>（<code>1</code> 行，<code>k</code> 列）或 <code>k x 1</code>（<code>k</code> 行，<code>1</code> 列）的形状建造，其中 <code>k</code> 可以是任意大小。两艘战舰之间至少有一个水平或垂直的空位分隔 （即没有相邻的战舰）。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/04/10/battelship-grid.jpg\" style=\"width: 333px; height: 333px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>board = [[\"X\",\".\",\".\",\"X\"],[\".\",\".\",\".\",\"X\"],[\".\",\".\",\".\",\"X\"]]\n",
    "<strong>输出：</strong>2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>board = [[\".\"]]\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == board.length</code></li>\n",
    "\t<li><code>n == board[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 200</code></li>\n",
    "\t<li><code>board[i][j]</code> 是 <code>'.'</code> 或 <code>'X'</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>你可以实现一次扫描算法，并只使用<strong> </strong><code>O(1)</code><strong> </strong>额外空间，并且不修改 <code>board</code> 的值来解决这个问题吗？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [battleships-in-a-board](https://leetcode.cn/problems/battleships-in-a-board/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [battleships-in-a-board](https://leetcode.cn/problems/battleships-in-a-board/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[\"X\",\".\",\".\",\"X\"],[\".\",\".\",\".\",\"X\"],[\".\",\".\",\".\",\"X\"]]', '[[\".\"]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        ans = 0\n",
    "        m, n = len(board), len(board[0])\n",
    "        for i, row in enumerate(board):\n",
    "            for j, ch in enumerate(row):\n",
    "                if ch == 'X':\n",
    "                    row[j] = '.'\n",
    "                    for k in range(j + 1, n):\n",
    "                        if row[k] != 'X':\n",
    "                            break\n",
    "                        row[k] = '.'\n",
    "                    for k in range(i + 1, m):\n",
    "                        if board[k][j] != 'X':\n",
    "                            break\n",
    "                        board[k][j] = '.'\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        m, n = len(board), len(board[0])\n",
    "        visited =  set()\n",
    "\n",
    "        def find(x, y):\n",
    "            if x<0 or y<0 or x>=m or y>=n or (x, y) in visited:\n",
    "                return False\n",
    "\n",
    "            visited.add(( x, y))\n",
    "\n",
    "            if board[x][y] == '.':\n",
    "                return False\n",
    "            \n",
    "            ret1 = find(x+1,y) or find(x-1, y)\n",
    "            if ret1:  return True\n",
    "            ret2 = find(x, y-1) or find(x, y+1)\n",
    "            if ret2: return True\n",
    "\n",
    "            return True\n",
    "\n",
    "        ret = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j]=='X' and (i,j) not in visited:\n",
    "                    if find(i,j):\n",
    "                        ret += 1\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        count = 0\n",
    "        unvisited = {\n",
    "            (i, j) for i in range (len(board)) for j in range(len(board[0]))\n",
    "            if board[i][j] == 'X'\n",
    "        }\n",
    "\n",
    "        def visit(i, j):\n",
    "            for i_move, j_move in [(-1, 0), (1, 0), (0, -1), (0, 1)]:\n",
    "                im, jm = i+i_move, j+j_move\n",
    "                if (im, jm) in unvisited:\n",
    "                    unvisited.remove((im, jm))\n",
    "                    visit(im, jm)\n",
    "\n",
    "        while unvisited:\n",
    "            curr = unvisited.pop()\n",
    "            count += 1\n",
    "            visit(*curr)\n",
    "\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "        class UF(object):\n",
    "            def __init__(self):\n",
    "                self.parants = list(range(m*n+1))\n",
    "                self.rank = [0] * (m*n+1)\n",
    "                self.cnt = 0\n",
    "            def find(self, x):\n",
    "                # print(x,m,n)\n",
    "                if self.parants[x] == x: return x\n",
    "                else: return self.find(self.parants[x])\n",
    "            def union(self, x, y):\n",
    "                par_x, par_y = self.find(x), self.find(y)\n",
    "                if par_x != par_y:\n",
    "                    if self.rank[par_x] == self.rank[par_y]: self.rank[par_x] += 1\n",
    "                    if self.rank[par_x] > self.rank[par_y]: self.parants[par_y] = par_x\n",
    "                    else: self.parants[par_x] = par_y\n",
    "                    self.cnt += 1\n",
    "        \n",
    "        uf = UF()\n",
    "        cnt = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == 'X':\n",
    "                    cnt += 1\n",
    "                    if j < n - 1 and board[i][j+1] == 'X': uf.union(n*i+j, n*i+j+1)\n",
    "                    if i < m - 1 and board[i+1][j] == 'X': uf.union(n*i+j, (i+1)*n+j)\n",
    "        \n",
    "        return cnt - uf.cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        s_visited = set()\n",
    "        m, n = len(board), len(board[0])\n",
    "        res = 0\n",
    "\n",
    "        def dps(i, j, dir):\n",
    "            nonlocal s_visited, m, n, res\n",
    "            if (i, j) not in s_visited:\n",
    "                s_visited.add((i, j))\n",
    "                if dir == 1:\n",
    "                    if i < m-1 and board[i+1][j] == 'X':\n",
    "                        dps(i+1, j, 1)\n",
    "                else:\n",
    "                    if j < n-1 and board[i][j+1] == 'X':\n",
    "                        dps(i, j+1, 2)\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == 'X' and (i, j) not in s_visited:\n",
    "                    res += 1\n",
    "                    if i < m-1 and board[i+1][j]=='X':\n",
    "                        dps(i, j, 1)\n",
    "                    else:\n",
    "                        dps(i, j, 2)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        if not board or len(board) == 0 or len(board[0]) == 0:\n",
    "            return 0\n",
    "        row, col = len(board), len(board[0])\n",
    "        res = 0\n",
    "        self.visited = set()\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if board[i][j] == 'X' and (i, j) not in self.visited:\n",
    "                    res = res + 1\n",
    "                    self.dfs(board, i, j)\n",
    "        return res\n",
    "    \n",
    "    def dfs(self, board, x, y):\n",
    "        self.visited.add((x, y))\n",
    "        dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n",
    "        for i, j in dirs:\n",
    "            nx, ny = x + i, y + j\n",
    "            if self.is_valid(board, nx, ny) and board[nx][ny] == 'X' and (nx, ny) not in self.visited:\n",
    "                self.dfs(board, nx, ny)\n",
    "    \n",
    "    def is_valid(self, board, x, y):\n",
    "        return x >= 0 and x < len(board) and y >= 0 and y < len(board[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        m, n = len(board), len(board[0])\n",
    "        ans = 0\n",
    "        direction = [[1, 0], [-1, 0], [0, 1], [0, -1]]\n",
    "        def dfs(i, j):\n",
    "            if board[i][j] == 'X':\n",
    "                board[i][j] = ''\n",
    "                for x, y in direction:\n",
    "                    xt = i + x\n",
    "                    yt = j + y\n",
    "                    if 0 <= xt <= m - 1 and 0 <= yt <= n - 1:\n",
    "                        dfs(xt, yt)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == 'X':\n",
    "                    ans += 1\n",
    "                    dfs(i, j)\n",
    "                    #print(board)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        sum = 0\n",
    "        for i in range(len(board)):\n",
    "            for j in range(len(board[0])):\n",
    "                if board[i][j] == '.':\n",
    "                    continue\n",
    "                direction = self.findDirection(board,i,j)\n",
    "                sum += 1\n",
    "                self.clearBoardAlongDir(board,i,j,direction)\n",
    "        return sum\n",
    "\n",
    "    def findDirection(self, board, i, j):\n",
    "        rows = len(board)\n",
    "        columns = len(board[0])\n",
    "        if i + 1 < rows and board[i+1][j] == 'X':\n",
    "            return 0\n",
    "        if j + 1 < columns and board[i][j+1] == 'X':\n",
    "            return 1\n",
    "        return -1\n",
    "\n",
    "    def clearBoardAlongDir(self, board, i, j, direction):\n",
    "        if direction == -1:\n",
    "            board[i][j] = '.'\n",
    "            return\n",
    "        if direction == 0:\n",
    "            while i < len(board) and board[i][j] == 'X':\n",
    "                board[i][j] = '.'\n",
    "                i += 1\n",
    "        else:\n",
    "            while j < len(board[0]) and board[i][j] == 'X':\n",
    "                board[i][j] = '.'\n",
    "                j += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "\n",
    "        m,n = len(board),len(board[0])\n",
    "        neighbor = [(0,1),(1,0)]\n",
    "        cnt = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == '.':\n",
    "                    continue\n",
    "                elif board[i][j] == 'X':\n",
    "                    cnt += 1\n",
    "                    board[i][j] == 'O'\n",
    "                    for x,y in neighbor:\n",
    "                        if i+x<m and j+y<n and board[i+x][j+y] == 'X':\n",
    "                            a,b = i+x,j+y\n",
    "                            while a<m and b<n and board[a][b] == 'X':\n",
    "                                board[a][b] = 'O'\n",
    "                                a+=x\n",
    "                                b+=y\n",
    "                            break\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        ans = 0\n",
    "        m = len(board[0])\n",
    "        n = len(board)\n",
    "        for i, row in enumerate(board):\n",
    "            for j, ch in enumerate(row):\n",
    "                if ch == 'X':\n",
    "                    row[j] = '.'\n",
    "                    for k in range(j + 1, m):\n",
    "                        if row[k] != 'X':\n",
    "                            break\n",
    "                        row[k] = '.'\n",
    "\n",
    "                    for k in range(i + 1, n):\n",
    "                        if board[k][j] != 'X':\n",
    "                            break\n",
    "                        board[k][j] = '.'\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        m, n = len(board),len(board[0])\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == \"X\" and \\\n",
    "                not ((i-1 >= 0 and board[i-1][j] == \"X\")) and \\\n",
    "                not ((j-1 >= 0 and board[i][j-1] == \"X\")):\n",
    "                    res += 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        row, col = len(board), len(board[0])\n",
    "        ans = 0 \n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if board[i][j] == 'X':\n",
    "                    self.dfs(board, i, j, row, col)\n",
    "                    ans += 1 \n",
    "        return ans \n",
    "                 \n",
    "\n",
    "    def dfs(self, board, rx, cx, row, col):\n",
    "        elem = board[rx][cx]\n",
    "        if elem != 'X':\n",
    "            return \n",
    "        board[rx][cx] = '.'\n",
    "        offset = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "        for ro, co in offset:\n",
    "            nr = rx + ro \n",
    "            nc = cx + co \n",
    "            if nr <= row -1 and nc <=col -1 and nr >=0 and nc >=0:\n",
    "                self.dfs(board, nr, nc, row, col)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        return sum(ch == 'X' and not (i > 0 and board[i - 1][j] == 'X' or j > 0 and board[i][j - 1] == 'X')\n",
    "                   for i, row in enumerate(board) for j, ch in enumerate(row))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        ans=0\n",
    "        m,n=len(board),len(board[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j]=='X':\n",
    "                    board[i][j]='.'\n",
    "                    for k in range(j+1,n):\n",
    "                        if board[i][k]!='X':\n",
    "                            break\n",
    "                        board[i][k]='.'\n",
    "                    for k in range(i+1,m):\n",
    "                        if board[k][j]!='X':\n",
    "                            break\n",
    "                        board[k][j]='.'\n",
    "                    ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        cnt = 0\n",
    "        for i in range(len(board)):\n",
    "            for j in range(len(board[0])):\n",
    "                if (board[i][j]=='X') and (i==0 or board[i-1][j]=='.') and (j==0 or board[i][j-1]=='.'):\n",
    "                    cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        rows = len(board)\n",
    "        cols = len(board[0])\n",
    "        res = 0\n",
    "        def dfs(board: List[List[str]], row: int, col: int):\n",
    "            if row < 0 or row > rows - 1 or col < 0 or col > cols - 1 or board[row][col] == '.':\n",
    "                return\n",
    "            board[row][col] = '.'\n",
    "            dfs(board, row + 1, col)\n",
    "            dfs(board, row, col + 1)\n",
    "\n",
    "        \n",
    "        for r in range(rows):\n",
    "            for c in range(cols):\n",
    "                if board[r][c] == 'X':\n",
    "                    res += 1\n",
    "                    dfs(board, r, c)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "DIRS = (0, 1), (1, 0), (0, -1), (-1, 0)\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        r, c = len(board), len(board[0])\n",
    "\n",
    "        def dfs_horizon(x, y):\n",
    "            nx, ny = x, y + 1\n",
    "            if  ny < c and board[nx][ny] == 'X':\n",
    "                board[nx][ny] = '.' \n",
    "                dfs_horizon(nx, ny)\n",
    "            return\n",
    "        \n",
    "\n",
    "        def dfs_vercital(x, y):\n",
    "            nx, ny = x+1, y\n",
    "            if nx < r and board[nx][ny] == 'X':\n",
    "                board[nx][ny] = '.'\n",
    "                dfs_vercital(nx, ny)\n",
    "            return\n",
    "        \n",
    "        count = 0\n",
    "        for i in range(r):\n",
    "            for j in range(c):\n",
    "                if board[i][j] == \"X\":\n",
    "                    count += 1\n",
    "                    dfs_horizon(i, j)\n",
    "                    dfs_vercital(i, j)\n",
    "        return count\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        m,n=len(board),len(board[0])\n",
    "        count=0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j]=='X':\n",
    "                    count+=1\n",
    "                    if i+1<m and board[i+1][j]=='X':\n",
    "                        k=i\n",
    "                        while k<m and board[k][j]=='X':\n",
    "                            board[k][j]='A'\n",
    "                            k+=1\n",
    "                    elif j+1<n and board[i][j+1]=='X':\n",
    "                        k=j\n",
    "                        while k<n and board[i][k]=='X':\n",
    "                            board[i][k]='A'\n",
    "                            k+=1\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        res=0\n",
    "        for i in range(len(board)):\n",
    "            for j in range(len(board[0])):\n",
    "                if board[i][j]=='X':\n",
    "                    board[i][j]='.'\n",
    "                    res+=1\n",
    "                    frontier=[[i,j]]\n",
    "                    while len(frontier)>0:\n",
    "                        x,y=frontier[0]\n",
    "                        if x+1<len(board) and board[x+1][y]=='X':\n",
    "                            frontier.append([x+1,y])\n",
    "                            board[x+1][y]='.'\n",
    "                        if y+1<len(board[0]) and board[x][y+1]=='X':\n",
    "                            frontier.append([x,y+1])\n",
    "                            board[x][y+1]='.'\n",
    "                        frontier.pop(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        m, n = len(board), len(board[0])\n",
    "        mk = [[0] * n for _ in range(m)]\n",
    "\n",
    "        def mkShip(aR, aC):\n",
    "            mk[aR][aC] = 1\n",
    "            if aC + 1 < n and 'X' == board[aR][aC + 1]:\n",
    "                aC += 1\n",
    "                while aC < n and board[aR][aC] == 'X':\n",
    "                    mk[aR][aC] = 1\n",
    "                    aC += 1\n",
    "            elif aR + 1 < m and 'X' == board[aR + 1][aC]:\n",
    "                aR += 1\n",
    "                while aR < m and board[aR][aC] == 'X':\n",
    "                    mk[aR][aC] = 1\n",
    "                    aR += 1\n",
    "\n",
    "        ret = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if 'X' == board[i][j] and 0 == mk[i][j]:\n",
    "                    \n",
    "                    mkShip(i, j)\n",
    "                    ret += 1\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        m, n = len(board), len(board[0])\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == 'X':\n",
    "                    if i > 0 and board[i-1][j] == 'X':\n",
    "                        continue\n",
    "                    if j > 0 and board[i][j-1] == 'X':\n",
    "                        continue\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == \".\":\n",
    "                    continue\n",
    "                if 0 < i and board[i-1][j] == \"X\":\n",
    "                    continue\n",
    "                if 0 < j and board[i][j-1] == \"X\":\n",
    "                    continue\n",
    "                ans += 1\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        count = 0\n",
    "        row = len(board)\n",
    "        col = len(board[0])\n",
    "        for r in range(row):\n",
    "            for c in range(col):\n",
    "                up_flag = 0\n",
    "                left_flag = 0\n",
    "                if board[r][c] == \"X\":\n",
    "                    if r - 1 >= 0 and board[r - 1][c] != \"X\":\n",
    "                        up_flag = 1\n",
    "                    if c - 1 >= 0 and board[r][c - 1] != \"X\":\n",
    "                        left_flag = 1\n",
    "                    if r - 1 < 0:\n",
    "                        up_flag = 1\n",
    "                    if c - 1 < 0:\n",
    "                        left_flag = 1  \n",
    "                    if up_flag == 1 and left_flag == 1:\n",
    "                        count += 1\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "        res = 0\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == '.':\n",
    "                    continue\n",
    "                if i>0 and board[i-1][j] == 'X':\n",
    "                    continue\n",
    "                if j >0 and board[i][j-1] == 'X':\n",
    "                    continue\n",
    "                res+=1\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        \n",
    "        #遇到board[i][j]==\"X\",res+1\n",
    "        #1.如果是垂直的，则看(i-1,j)这个坐标，如果也有X，那么是垂直相邻不满足res-1\n",
    "        #2.如果横着的，kan(i,j-1)这个部分，如果也有X，那么是水平相邻，res-1\n",
    "        m=len(board)#行数\n",
    "        n=len(board[0])#列数\n",
    "        res=0\n",
    "        for i in range(m):#统计水平总数\n",
    "            for j in range(n):#统计垂直总数\n",
    "                if board[i][j]=='X':\n",
    "                    res+=1\n",
    "                    if i>0 and board[i-1][j]=='X':\n",
    "                        res-=1\n",
    "                    if j>0 and board[i][j-1]=='X':\n",
    "                        res-=1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        m, n = len(board), len(board[0])\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == 'X':\n",
    "                    if i > 0 and board[i - 1][j] == 'X':\n",
    "                        continue\n",
    "                    if j > 0 and board[i][j - 1] == 'X':\n",
    "                        continue\n",
    "                    ans += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        ans = 0\n",
    "        m, n = len(board), len(board[0])\n",
    "        for i, row in enumerate(board):\n",
    "            for j, ch in enumerate(row):\n",
    "                if ch == 'X':\n",
    "                    row[j] = '.'\n",
    "                    for k in range(j + 1, n):\n",
    "                        if row[k] != 'X':\n",
    "                            break\n",
    "                        row[k] = '.'\n",
    "                    for k in range(i + 1, m):\n",
    "                        if board[k][j] != 'X':\n",
    "                            break\n",
    "                        board[k][j] = '.'\n",
    "                    ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        height=len(board)\n",
    "        width=len(board[0])\n",
    "        result=0\n",
    "        for y in range(height):\n",
    "            for x in range(width):\n",
    "                if board[y][x]=='.':\n",
    "                    continue\n",
    "                if y>0 and board[y-1][x]=='X':\n",
    "                    continue\n",
    "                if x>0 and board[y][x-1]=='X':\n",
    "                    continue\n",
    "                result+=1\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        m,n = len(board), len(board[0])\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == 'X':\n",
    "                    if i>0 and j>0:\n",
    "                        if board[i-1][j]=='.' and board[i][j-1]=='.':\n",
    "                            ans += 1\n",
    "                    elif i==0 and j>0:\n",
    "                        if board[i][j-1]=='.':\n",
    "                            ans += 1\n",
    "                    elif j==0 and i>0:\n",
    "                        if board[i-1][j]=='.':\n",
    "                            ans += 1\n",
    "                    elif i==0 and j==0:\n",
    "                        ans += 1\n",
    "\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        return sum(board[i][j] == 'X' and (i == 0 or board[i-1][j] == '.') and (j == 0 or board[i][j-1] == '.') for i in range(len(board)) for j in range(len(board[0])))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        m, n = len(board), len(board[0])\n",
    "        mk = [[0] * n for _ in range(m)]\n",
    "\n",
    "        def mkShip(aR, aC):\n",
    "            mk[aR][aC] = 1\n",
    "            if aC + 1 < n and 'X' == board[aR][aC + 1]:\n",
    "                aC += 1\n",
    "                while aC < n and board[aR][aC] == 'X':\n",
    "                    mk[aR][aC] = 1\n",
    "                    aC += 1\n",
    "            elif aR + 1 < m and 'X' == board[aR + 1][aC]:\n",
    "                aR += 1\n",
    "                while aR < m and board[aR][aC] == 'X':\n",
    "                    mk[aR][aC] = 1\n",
    "                    aR += 1\n",
    "\n",
    "        ret = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if 'X' == board[i][j] and 0 == mk[i][j]:\n",
    "                    \n",
    "                    mkShip(i, j)\n",
    "                    ret += 1\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from  typing import  List\n",
    "class Solution:\n",
    "    def dfs(self,x,y,m,n,f,board,cnt):\n",
    "        if x<0 or x>=m or y<0 or y>=n or board[x][y]=='.':\n",
    "            return\n",
    "\n",
    "        if y+1 < n and board[x][y+1] == 'X' and f[x][y+1] == 0:\n",
    "            f[x][y+1]=cnt\n",
    "            self.dfs(x,y+1,m,n,f,board,cnt)\n",
    "        if y-1 >= 0 and board[x][y-1] == 'X' and f[x][y-1] == 0:\n",
    "            f[x][y-1]=cnt\n",
    "            self.dfs(x,y-1,m,n,f,board,cnt)\n",
    "        if x+1 < m and board[x+1][y] == 'X' and f[x+1][y] == 0:\n",
    "            f[x+1][y]=cnt\n",
    "            self.dfs(x+1,y,m,n,f,board,cnt)\n",
    "        if x-1 >=0 and board[x-1][y] == 'X' and f[x-1][y] == 0:\n",
    "            f[x-1][y]=cnt\n",
    "            self.dfs(x-1,y,m,n,f,board,cnt)\n",
    "\n",
    "\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        m, n = len(board), len(board[0])\n",
    "        f = [[0]*n for _ in range(m)]\n",
    "        cnt=1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j]=='X' and f[i][j]==0:\n",
    "                    f[i][j]=cnt\n",
    "                    self.dfs(i,j,m,n,f,board,cnt)\n",
    "                    cnt+=1\n",
    "        return cnt-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        m=len(board)\n",
    "        n=len(board[0])\n",
    "        v=[[False for i in range(n)]for i in range(m)]\n",
    "        ans=0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if not v[i][j] and board[i][j]=='X':\n",
    "                    v[i][j]=True\n",
    "                    for k in range(j+1,n):\n",
    "                        if board[i][k]=='.':\n",
    "                            v[i][k]=True\n",
    "                            break\n",
    "                        v[i][k]=True\n",
    "                    for k in range(i+1,m):\n",
    "                        if board[k][j]=='.':\n",
    "                            v[k][j]=True\n",
    "                            break\n",
    "                        v[k][j]=True\n",
    "                    ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, board: List[List[str]], flag: List[List[int]], idx):\n",
    "        if idx[0] < 0 or idx[0] >= len(board) or idx[1] < 0 or idx[1] >= len(board[0]):\n",
    "            return\n",
    "        if flag[idx[0]][idx[1]] == 1:\n",
    "            return\n",
    "        if board[idx[0]][idx[1]] == '.':\n",
    "            return\n",
    "        else:\n",
    "            flag[idx[0]][idx[1]] = 1\n",
    "            self.dfs(board, flag, (idx[0] + 1, idx[1]))\n",
    "            self.dfs(board, flag, (idx[0] - 1, idx[1]))\n",
    "            self.dfs(board, flag, (idx[0], idx[1] + 1))\n",
    "            self.dfs(board, flag, (idx[0], idx[1] - 1))\n",
    "\n",
    "\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        flag = [[0 for _ in range(len(board[0]))] for _ in range(len(board))]\n",
    "        cnt = 0\n",
    "        for i in range(len(board)):\n",
    "            for j in range(len(board[0])):\n",
    "                if flag[i][j] == 0 and board[i][j] == 'X':\n",
    "                    cnt += 1\n",
    "                    self.dfs(board, flag, (i, j))\n",
    "                    \n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "        ans = 0\n",
    "        visited = [[False] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if visited[i][j] == True:\n",
    "                    continue\n",
    "                visited[i][j] = True\n",
    "                if board[i][j] == '.': continue\n",
    "                ans += 1\n",
    "                if i > 0 and board[i - 1][j] == 'X':\n",
    "                    k = i - 1\n",
    "                    while k >= 0 and board[k][j] == 'X':\n",
    "                        visited[k][j] = True\n",
    "                        k -= 1\n",
    "                if j > 0 and board[i][j - 1] == 'X':\n",
    "                    k = j - 1\n",
    "                    while k >= 0 and board[i][k] == 'X':\n",
    "                        visited[i][k] = True\n",
    "                        k -= 1\n",
    "                if i < m - 1 and board[i + 1][j] == 'X':\n",
    "                    k = i + 1\n",
    "                    while k <= m - 1 and board[k][j] == 'X':\n",
    "                        visited[k][j] = True\n",
    "                        k += 1\n",
    "                if j < n - 1 and board[i][j + 1] == 'X':\n",
    "                    k = j + 1\n",
    "                    while k <= n - 1 and board[i][k] == 'X':\n",
    "                        visited[i][k] = True\n",
    "                        k += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        dir_ = [[-1, 0], [1, 0], [0, 1], [0, -1]]\n",
    "        visited = [[False] * len(board[0]) for _ in range(len(board))]\n",
    "        def dfs(x, y, visited, board):\n",
    "            if visited[x][y] or board[x][y] == '.':\n",
    "                return\n",
    "            visited[x][y] = True\n",
    "            for i in range(4):\n",
    "                next_x, next_y = x + dir_[i][0], y + dir_[i][1]\n",
    "                if next_x < 0 or next_x >= len(board) or next_y < 0 or next_y >= len(board[0]):\n",
    "                    continue\n",
    "                dfs(next_x, next_y, visited, board)\n",
    "\n",
    "        res = 0\n",
    "        for i in range(len(board)):\n",
    "            for j in range(len(board[0])):\n",
    "                if not visited[i][j] and board[i][j] == 'X':\n",
    "                    res += 1\n",
    "                    dfs(i, j, visited, board)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\n",
    "# @lc app=leetcode.cn id=419 lang=python\n",
    "#\n",
    "# [419] 甲板上的战舰\n",
    "#\n",
    "\n",
    "# @lc code=start\n",
    "class Solution(object):\n",
    "    def countBattleships(self, board):\n",
    "        \"\"\"\n",
    "        :type board: List[List[str]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        col = len(board[0])\n",
    "        row = len(board)\n",
    "        check_map = [[0]*(col + 2) for i in range(row + 2)]\n",
    "        num = 0\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if board[i][j] ==\"X\":\n",
    "                    if check_map[i][j+1] == 0 and check_map[i+1][j] == 0:\n",
    "                        num += 1\n",
    "                        check_map[i+1][j+1] = num\n",
    "                    else:\n",
    "                        check_map[i+1][j+1] = max(check_map[i][j+1],check_map[i + 1][j])\n",
    "        \n",
    "        return num\n",
    "# @lc code=end\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        moves = [[0,1],[0,-1],[1,0],[-1,0]]\n",
    "\n",
    "        def dfs(rIdx, cIdx, board, visited):\n",
    "            nonlocal moves\n",
    "            visited.append((rIdx, cIdx))\n",
    "            for move in moves:\n",
    "                tR = rIdx + move[0]\n",
    "                tC = cIdx + move[1]\n",
    "                if tR >= 0 and tR < len(board) and tC >= 0 and tC < len(board[0]) and board[tR][tC] == 'X' and (not (tR, tC) in visited):\n",
    "                    dfs(tR, tC, board, visited)\n",
    "\n",
    "        ans = 0\n",
    "        visited = []\n",
    "        for i in range(len(board)):\n",
    "            for j in range(len(board[0])):\n",
    "                if board[i][j] == 'X' and (not (i, j) in visited):\n",
    "                    dfs(i, j, board, visited)\n",
    "                    ans += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        m, n = len(board), len(board[0])\n",
    "        print(m, n)\n",
    "        ret = 0\n",
    "        for r, row in enumerate(board):\n",
    "            for c, val in enumerate(row):\n",
    "                if val == \"X\":\n",
    "                    row[c] = \".\"\n",
    "                    for k in range(c + 1, n):\n",
    "                        if row[k] != \"X\":\n",
    "                            break\n",
    "                        row[k] = \".\"\n",
    "                    for k in range(r + 1, m):\n",
    "                        if board[k][c] != \"X\":\n",
    "                            break \n",
    "                        board[k][c] = \".\"\n",
    "                    ret += 1\n",
    "                print(ret)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    res = 0\n",
    "\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "        boardlist = []\n",
    "        for i in range(m):\n",
    "            boardlist.append([0] * n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == 'X':\n",
    "                    boardlist[i][j] = 1\n",
    "                else:\n",
    "                    boardlist[i][j] = 0\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if boardlist[i][j] == 1:\n",
    "                    self.getnum(i, j, boardlist)\n",
    "                    self.res += 1\n",
    "\n",
    "        return self.res\n",
    "\n",
    "    def getnum(self, x: int, y: int, boardlist: List[List[int]]) -> None:\n",
    "        m = len(boardlist)\n",
    "        n = len(boardlist[0])\n",
    "        # 上下链\n",
    "        if x - 1 >= 0:\n",
    "            if boardlist[x - 1][y] == 1:\n",
    "                # 清除该列与点链接的所有1\n",
    "                left = x\n",
    "                while left - 1 >= 0:\n",
    "                    if boardlist[left - 1][y] == 1:\n",
    "                        left -= 1\n",
    "                    else:\n",
    "                        break\n",
    "                right = x\n",
    "                while right + 1 < m:\n",
    "                    if boardlist[right + 1][y] == 1:\n",
    "                        right += 1\n",
    "                    else:\n",
    "                        break\n",
    "                for i in range(left, right + 1, 1):\n",
    "                    boardlist[i][y] = 0\n",
    "                return \n",
    "        if x + 1 < m:\n",
    "            if boardlist[x + 1][y] == 1:\n",
    "                # 清除该列与点链接的所有1\n",
    "                left = x\n",
    "                while left - 1 >= 0:\n",
    "                    if boardlist[left - 1][y] == 1:\n",
    "                        left -= 1\n",
    "                    else:\n",
    "                        break\n",
    "                right = x\n",
    "                while right + 1 < m:\n",
    "                    if boardlist[right + 1][y] == 1:\n",
    "                        right += 1\n",
    "                    else:\n",
    "                        break\n",
    "                for i in range(left, right + 1, 1):\n",
    "                    boardlist[i][y] = 0\n",
    "                return \n",
    "            \n",
    "        # 左右链\n",
    "        if y - 1 >= 0:\n",
    "            if boardlist[x][y - 1] == 1:\n",
    "                # 清除该列与点链接的所有1\n",
    "                left = y\n",
    "                while left - 1 >= 0:\n",
    "                    if boardlist[x][left - 1] == 1:\n",
    "                        left -= 1\n",
    "                    else:\n",
    "                        break\n",
    "                right = y\n",
    "                while right + 1 < n:\n",
    "                    if boardlist[x][right + 1] == 1:\n",
    "                        right += 1\n",
    "                    else:\n",
    "                        break\n",
    "                for i in range(left, right + 1, 1):\n",
    "                    boardlist[x][i] = 0\n",
    "                return \n",
    "        if y + 1 < n:\n",
    "            if boardlist[x][y + 1] == 1:\n",
    "                # 清除该列与点链接的所有1\n",
    "                left = y\n",
    "                while left - 1 >= 0:\n",
    "                    if boardlist[x][left - 1] == 1:\n",
    "                        left -= 1\n",
    "                    else:\n",
    "                        break\n",
    "                right = y\n",
    "                while right + 1 < n:\n",
    "                    if boardlist[x][right + 1] == 1:\n",
    "                        right += 1\n",
    "                    else:\n",
    "                        break\n",
    "                for i in range(left, right + 1, 1):\n",
    "                    boardlist[x][i] = 0\n",
    "                return \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        m,n = len(board),len(board[0])\n",
    "        temp = []\n",
    "        count = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == \"X\" :\n",
    "                    temp.append([i+1,j])\n",
    "                    temp.append([i,j+1])\n",
    "                    if ([i,j] not in temp):\n",
    "                        count +=1 \n",
    "        return count\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BoardMap():\n",
    "    def __init__(self, board):\n",
    "        self.board = board\n",
    "        self.m = len(board)\n",
    "        self.n = len(board[0])\n",
    "\n",
    "    def get(self, i, j):\n",
    "        if 0 <= i <= self.m -1 and 0 <= j <= self.n -1 :\n",
    "            return self.board[i][j]\n",
    "        else:\n",
    "            return None\n",
    "\n",
    "class Solution:\n",
    "\n",
    "\n",
    "    def countBattleships(self, board):\n",
    "        bd = BoardMap(board)\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "        mn = max(m,n)\n",
    "        \n",
    "        scanned = [[False for j in range(n)] for i in range(m)]\n",
    "\n",
    "        cnt = 0\n",
    "\n",
    "        def mark_entire_ship(i,j):\n",
    "            direction = None\n",
    "            scanned[i][j] = True\n",
    "\n",
    "            if bd.get(i+1,j)=='X' or bd.get(i-1,j)=='X':\n",
    "                direction = 'i'\n",
    "\n",
    "            if bd.get(i,j+1)=='X' or bd.get(i,j-1)=='X':\n",
    "                direction = 'j'\n",
    "\n",
    "            if direction == 'i':\n",
    "                for delta_i in range(mn):\n",
    "                    if bd.get(i+delta_i, j) == 'X':\n",
    "                        scanned[i+delta_i][j] = True\n",
    "                    else:\n",
    "                        break\n",
    "                for delta_i in range(mn):\n",
    "                    if bd.get(i-delta_i, j) == 'X':\n",
    "                        scanned[i-delta_i][j] = True\n",
    "                    else:\n",
    "                        break\n",
    "            if direction == 'j':\n",
    "                for delta_j in range(mn):\n",
    "                    if bd.get(i, j+delta_j) == 'X':\n",
    "                        scanned[i][j+delta_j] = True\n",
    "                    else:\n",
    "                        break\n",
    "                for delta_j in range(mn):\n",
    "                    if bd.get(i, j-delta_j) == 'X':\n",
    "                        scanned[i][j-delta_j] = True\n",
    "                    else:\n",
    "                        break\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if scanned[i][j]: continue\n",
    "                if board[i][j]=='X':\n",
    "                    cnt += 1\n",
    "                    # mark entire ship\n",
    "                    scanned[i][j] = True\n",
    "                    mark_entire_ship(i,j)\n",
    "                    # print(scanned)\n",
    "                else:\n",
    "                    scanned[i][j] = True\n",
    "\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        m,n = len(board),len(board[0])\n",
    "        temp = []\n",
    "        count = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == \"X\" :\n",
    "                    temp.append([i+1,j])\n",
    "                    temp.append([i,j+1])\n",
    "                    if ([i,j] not in temp):\n",
    "                        count +=1 \n",
    "        return count\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "        self.ans = 0\n",
    "        mark = [[False]*n for i in range(m)]\n",
    "\n",
    "        def bfs(i, j):\n",
    "            q = [[i, j]]\n",
    "            while q:\n",
    "                temp = q\n",
    "                q = []\n",
    "                for i,j in temp:\n",
    "                    print(i,j)\n",
    "                    mark[i][j] = True\n",
    "                    if i>0 and not mark[i-1][j] and board[i-1][j] == 'X':\n",
    "                        q.append([i-1, j])\n",
    "                    if j>0 and not mark[i][j-1] and board[i][j-1] == 'X':\n",
    "                        q.append([i, j-1])\n",
    "                    if i<m-1 and not mark[i+1][j] and board[i+1][j]== 'X':\n",
    "                        q.append([i+1, j])\n",
    "                    if j<n-1 and not mark[i][j+1] and board[i][j+1]== 'X':\n",
    "                        q.append([i, j+1])\n",
    "            self.ans += 1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == 'X' and not mark[i][j]:\n",
    "                    print('in', i, j)\n",
    "                    bfs(i, j)\n",
    "        return self.ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        m,n=len(board),len(board[0])\n",
    "        links=[]\n",
    "        res=0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j]=='X':\n",
    "                    if (i,j) not in links:\n",
    "                        res+=1\n",
    "                    links+=[(i+1,j),(i,j+1)]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "\n",
    "        dp = []\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == \"X\":\n",
    "                    if [i, j] not in dp:\n",
    "                        #把它周围两个方向都找一遍，右边和下面直到遇到\".\"\n",
    "                        ans += 1\n",
    "                        dp.append([i,j])\n",
    "                        #右边\n",
    "                        k = j+1\n",
    "                        while k < n:\n",
    "                            if board[i][k] == \".\":\n",
    "                                break\n",
    "                            else:\n",
    "                                dp.append([i,k])\n",
    "                                k+=1\n",
    "                        #下面\n",
    "                        l = i+1\n",
    "                        while l < m:\n",
    "                            if board[l][j] == \".\":\n",
    "                                break\n",
    "                            else:\n",
    "                                dp.append([l,j])\n",
    "                                l+=1\n",
    "        print(dp)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        used=[[0]*len(board[0])for _ in range(len(board))]\n",
    "        def check(i,j):\n",
    "            used[i][j]=1\n",
    "            if board[i][j]!='X':\n",
    "                return\n",
    "            if i-1>0 and used[i-1][j]!=1:\n",
    "                check(i-1,j)\n",
    "            if i+1<len(used) and used[i+1][j]!=1:\n",
    "                check (i+1,j)\n",
    "            if j-1>0 and used[i][j-1]!=1:\n",
    "                check(i,j-1)\n",
    "            if j+1<len(used[0]) and used[i][j+1]!=1:\n",
    "                check(i,j+1)\n",
    "        ret=0\n",
    "        for i in range(len(used)):\n",
    "            for j in range(len(used[0])):\n",
    "                if used[i][j]!=1:\n",
    "                    if board[i][j]=='X':\n",
    "                        ret+=1\n",
    "                    check(i,j)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "\n",
    "        sea = [0] * (m + 2)\n",
    "        for i in range(m + 2):\n",
    "            sea[i] = [0] * (n + 2)\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if(board[i][j] == \"X\"):\n",
    "                    sea[i+1][j+1] = 1\n",
    "                else:\n",
    "                    sea[i+1][j+1] = 0\n",
    "        \n",
    "        v = [0] * (m + 2)\n",
    "        for i in range(m + 2):\n",
    "            v[i] = [0] * (n + 2)\n",
    "        \n",
    "        c = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if(sea[i+1][j+1] == 1 and v[i+1][j+1] == 0):\n",
    "                    c = c + 1\n",
    "                    stack = []\n",
    "                    stack.append([i+1,j+1])\n",
    "                    while(len(stack) != 0):\n",
    "                        temp = stack.copy()\n",
    "                        stack = []\n",
    "                        for k in range(len(temp)):\n",
    "                            v[temp[k][0]][temp[k][1]] = 1\n",
    "                        for k in range(len(temp)):\n",
    "                            p = 1\n",
    "                            while(sea[temp[k][0]-p][temp[k][1]] == 1 and v[temp[k][0]-p][temp[k][1]] == 0):\n",
    "                                stack.append([temp[k][0]-p,temp[k][1]])\n",
    "                                p = p + 1\n",
    "\n",
    "                            p = 1\n",
    "                            while(sea[temp[k][0]+p][temp[k][1]] == 1 and v[temp[k][0]+p][temp[k][1]] == 0):\n",
    "                                stack.append([temp[k][0]+p,temp[k][1]])\n",
    "                                p = p + 1\n",
    "\n",
    "                            p = 1\n",
    "                            while(sea[temp[k][0]][temp[k][1]-p] == 1 and v[temp[k][0]][temp[k][1]-p] == 0):\n",
    "                                stack.append([temp[k][0],temp[k][1]-p])\n",
    "                                p = p + 1\n",
    "\n",
    "                            p = 1\n",
    "                            while(sea[temp[k][0]][temp[k][1]+p] == 1 and v[temp[k][0]][temp[k][1]+p] == 0):\n",
    "                                stack.append([temp[k][0],temp[k][1]+p])\n",
    "                                p = p + 1\n",
    "        \n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        m,n = len(board),len(board[0])\n",
    "        parent = {(x,y):(x,y) for x  in range(m) for y in range(n) if board[x][y] == 'X'}\n",
    "        rank = {(x,y):1 for x  in range(m) for y in range(n) if board[x][y] == 'X'}\n",
    "        self.count = 0\n",
    "        def find(i):\n",
    "            if parent[i] != i:\n",
    "                parent[i] = find(parent[i])\n",
    "            return parent[i]\n",
    "        def merge(i,j):\n",
    "            ri,rj = find(i),find(j)\n",
    "            if ri != rj:\n",
    "                if rank[rj] > rank[ri]:\n",
    "                    ri,rj = rj,ri\n",
    "                parent[rj] = ri\n",
    "                rank[ri] += rank[rj]\n",
    "                self.count -= 1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == 'X':\n",
    "                    self.count += 1\n",
    "                    for x,y in [[i+1,j],[i,j-1]]:\n",
    "                        if 0<=x<m and 0<=y<n and board[x][y] == 'X':\n",
    "                            merge((x,y),(i,j))\n",
    "        return self.count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        m, n = len(board), len(board[0])\n",
    "\n",
    "        ret = 0\n",
    "        visited = [[0] * n for _ in range(m)]\n",
    "        ds = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n",
    "        def dfs(x, y):\n",
    "            visited[x][y] = 1\n",
    "\n",
    "            for d in ds:\n",
    "                row, col = x + d[0], y + d[1]\n",
    "                if row < 0 or row >= m or col < 0 or col >= n \\\n",
    "                   or visited[row][col] == 1 or board[row][col] == \".\":\n",
    "                   continue\n",
    "                dfs(row, col)\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if visited[i][j] == 0 and board[i][j] == \"X\":\n",
    "                    ret += 1\n",
    "                    dfs(i, j)\n",
    "\n",
    "        return ret\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self, M):\n",
    "        self.parent = [0] * M\n",
    "        self.size = [0] * M\n",
    "        self.cnt = 0\n",
    "        for i in range(M):\n",
    "            self.parent[i] = i\n",
    "            self.size[i] = 1\n",
    "            self.cnt += 1\n",
    "    def find(self, x): \n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "            return self.parent[x]\n",
    "        return x\n",
    "    def connected(self, p, q):\n",
    "        return self.find(p) == self.find(q)\n",
    "    def union(self, p, q):\n",
    "        if self.connected(p, q): return\n",
    "        leader_p, leader_q = self.find(p), self.find(q)\n",
    "        if self.size[leader_p] >= self.size[leader_q]:\n",
    "            self.parent[leader_q] = leader_p\n",
    "            self.size[leader_p] += self.size[leader_q]\n",
    "        else:\n",
    "            self.parent[leader_p] = leader_q\n",
    "            self.size[leader_q] += self.size[leader_p]\n",
    "        self.cnt -= 1\n",
    "    \n",
    "class Solution: \n",
    "    def countBattleships(self, board: List[List[str]]) -> int: \n",
    "        m, n = len(board), len(board[0])\n",
    "        lis = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == \"X\":\n",
    "                    lis.append([i, j])\n",
    "        M = len(lis)\n",
    "        uf = UF(M)\n",
    "        for i in range(M-1):\n",
    "            for j in range(i+1, M):\n",
    "                x1, y1 = lis[i]\n",
    "                x2, y2 = lis[j]\n",
    "                if [x1, y1] in [[x2-1, y2], [x2+1, y2], [x2, y2-1], [x2, y2+1]]:\n",
    "                    uf.union(i, j)\n",
    "        return uf.cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        m, n = len(board), len(board[0]) \n",
    "        vis = [[0] * n for _ in range(m)]\n",
    "        ans = 0 \n",
    "        def dfs(x, y):\n",
    "            vis[x][y] = 1\n",
    "            for [nx, ny] in [[x+1, y], [x-1, y], [x, y+1], [x, y-1]]:\n",
    "                if 0<=nx<m and 0<=ny<n and board[nx][ny] == 'X' and not vis[nx][ny]:\n",
    "                    dfs(nx, ny)\n",
    "            \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == 'X' and not vis[i][j]:\n",
    "                    ans += 1\n",
    "                    dfs(i, j)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        row, col = len(board), len(board[0])\n",
    "        flag_matrix = [[False for _ in range(col)] for k in range(row)]\n",
    "        self.result = 0\n",
    "        def dfs(i, j, num):\n",
    "            if flag_matrix[i][j]:\n",
    "                return\n",
    "            flag_matrix[i][j] = True\n",
    "            if num == 1:\n",
    "                self.result += 1\n",
    "            # up\n",
    "            if i - 1 >= 0  and board[i - 1][j] == 'X':\n",
    "                dfs(i-1, j, num+1)\n",
    "            # down\n",
    "            if i + 1 < row and board[i + 1][j] == 'X':\n",
    "                dfs(i+1, j, num+1)\n",
    "            # left\n",
    "            if j - 1 >= 0 and board[i][j - 1] == 'X':\n",
    "                dfs(i, j-1, num+1)\n",
    "            # right\n",
    "            if j + 1 < col and board[i][j + 1] == 'X':\n",
    "                dfs(i, j+1, num+1)\n",
    "        \n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if board[i][j] == 'X':\n",
    "                    dfs(i,j,1)\n",
    "        return self.result\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        m, n = len(board), len(board[0])\n",
    "        links = []\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == 'X': #是战舰\n",
    "                    if (i, j) not in links:\n",
    "                        res += 1\n",
    "                    links += [(i+1, j), (i, j+1)]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        s1=set()\n",
    "        m=len(board)\n",
    "        n=len(board[0])\n",
    "        t=0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j]=='X' and (i,j) not in s1:\n",
    "                    t=t+1\n",
    "                    s1.add((i,j))\n",
    "                    k=1\n",
    "                    while i+k<m and board[i+k][j]=='X':\n",
    "                        s1.add((i+k,j))\n",
    "                        k=k+1\n",
    "                    k=1\n",
    "                    while j+k<n and board[i][j+k]=='X':\n",
    "                        s1.add((i,j+k))\n",
    "                        k=k+1\n",
    "        return t\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "    #当前点是否是x 传递下个点给定方向，\n",
    "    def find_one(self, point, visited, delta, board):\n",
    "        n, m = point\n",
    "        if point not in visited and n < len(board) and m < len(board[0]) and board[n][m] == 'X':\n",
    "            visited.add(point)\n",
    "            next_point = (n + delta[0], m + delta[1])\n",
    "            self.find_one(next_point, visited, delta, board)\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        visited = set()\n",
    "        #遍历矩阵，有x向右、下两个方向找x，有则记录方向，m n截止，count+1\n",
    "        count = 0\n",
    "        for n in range(len(board)):\n",
    "            for m in range(len(board[0])):\n",
    "                if (n,m) not in visited and board[n][m] == 'X':\n",
    "                    visited.add((n, m))\n",
    "                    count += 1\n",
    "                    self.find_one((n, m+1),visited, (0, 1), board)\n",
    "                    self.find_one((n+1, m),visited, (1, 0), board)\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        dx = (0,0,-1,1)\n",
    "        dy = (1,-1,0,0)\n",
    "        m,n = len(board),len(board[0])\n",
    "        @cache\n",
    "        def helper(i:int,j:int):\n",
    "            if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != 'X':\n",
    "                return \n",
    "            board[i][j] = '#'\n",
    "            for k in range(4):\n",
    "                helper(i + dx[k],j + dy[k])\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == 'X':\n",
    "                    ans += 1\n",
    "                    helper(i,j)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        self.visited = set()\n",
    "        self.board = board\n",
    "        self.xlim = len(board)\n",
    "        self.ylim = len(board[0])\n",
    "        ans = 0\n",
    "        for x in range(self.xlim):\n",
    "            for y in range(self.ylim):\n",
    "                if (x, y) not in self.visited and board[x][y] == 'X':\n",
    "                    ans += 1\n",
    "                    self.visited.add((x, y))\n",
    "                    self.dfs(x+1, y, 0)\n",
    "                    self.dfs(x-1, y, 1)\n",
    "                    self.dfs(x, y+1, 2)\n",
    "                    self.dfs(x, y-1, 3)\n",
    "\n",
    "        return ans\n",
    "\n",
    "    def dfs(self, x, y, d):\n",
    "        if 0 <= x < self.xlim and 0 <= y < self.ylim and self.board[x][y] == \"X\":\n",
    "            self.visited.add((x, y))\n",
    "            if d == 0: \n",
    "                self.dfs(x+1, y, d)\n",
    "            elif d == 1:\n",
    "                self.dfs(x-1, y, d)\n",
    "            elif d == 2:\n",
    "                self.dfs(x, y+1, d)\n",
    "            else:\n",
    "                self.dfs(x, y-1, d)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "direction = [-1, 0, 1, 0, -1]\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        m, n = len(board), len(board[0])\n",
    "\n",
    "        seen = defaultdict(bool)\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        def dfs(x, y):\n",
    "            for k in range(4):\n",
    "                a = x + direction[k]\n",
    "                b = y + direction[k + 1]\n",
    "                if 0 <= a < m and 0 <= b < n and not seen[a, b] and board[a][b] == 'X':\n",
    "                    seen[a, b] = True\n",
    "                    dfs(a, b)\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == 'X' and not seen[i, j]:\n",
    "                    seen[i, j] = True\n",
    "                    ans += 1\n",
    "                    dfs(i, j)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        self.visited = set()\n",
    "        self.dirs = [(1, 0), (0, 1)]\n",
    "        self.rowNum = len(board)\n",
    "        self.colNum = len(board[0])\n",
    "        ans = 0\n",
    "\n",
    "        for rowIdx in range(self.rowNum):\n",
    "            for colIdx in range(self.colNum):\n",
    "                if board[rowIdx][colIdx] == 'X' and (rowIdx, colIdx) not in self.visited:\n",
    "                    ans += 1\n",
    "                    self.BFS([(rowIdx, colIdx)], board)\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "    def BFS(self, queue, board):\n",
    "        while queue:\n",
    "            rowIdx, colIdx = queue.pop()\n",
    "            self.visited.add((rowIdx, colIdx))\n",
    "            for dir in self.dirs:\n",
    "                newRowIdx = rowIdx + dir[0]\n",
    "                newColIdx = colIdx + dir[1]\n",
    "                if newRowIdx < self.rowNum and newColIdx < self.colNum and board[newRowIdx][newColIdx] == 'X' and (newRowIdx, newColIdx) not in self.visited:\n",
    "                    queue.append((newRowIdx, newColIdx))\n",
    "\n",
    "            \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        #岛屿问题简单版\n",
    "        ret = 0\n",
    "        dic = {}\n",
    "        def dfs(i,j,row,col):\n",
    "            if i < 0 or j < 0 or i >= row or j >= col:return\n",
    "            if board[i][j] != 'X':return\n",
    "            dic[(i,j)] = 1\n",
    "            dfs(i+1,j,row,col)\n",
    "            dfs(i,j+1,row,col)\n",
    "        row,col = len(board),len(board[0])\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if board[i][j] == 'X' and (i,j) not in dic:\n",
    "                    dfs(i,j,row,col)\n",
    "                    ret += 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "        seen = set()\n",
    "\n",
    "        M = len(board)\n",
    "        N = len(board[0])\n",
    "\n",
    "        def bfs(pos):\n",
    "            deque = collections.deque([pos])\n",
    "            seen.add(pos)\n",
    "\n",
    "            while len(deque) > 0:\n",
    "                position = deque.popleft()\n",
    "                for direction in [(0, 1), (0, -1), (-1, 0), (1, 0)]:\n",
    "                    newX = position[0] + direction[0]\n",
    "                    newY = position[1] + direction[1]\n",
    "\n",
    "                    if newX < 0 or newX >= M or newY < 0 or newY >= N:\n",
    "                        continue\n",
    "                    \n",
    "                    if (newX, newY) not in seen and board[newX][newY] == \"X\":\n",
    "                        seen.add((newX, newY))\n",
    "                        bfs((newX, newY))\n",
    "        \n",
    "        counter = 0\n",
    "        for x in range(M):\n",
    "            for y in range(N):\n",
    "                if (x, y) not in seen and board[x][y] == \"X\":\n",
    "                    counter += 1\n",
    "                    bfs((x, y))\n",
    "\n",
    "        return counter\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "\n",
    "        def DFS(x, y) -> None:\n",
    "            visited.add((x, y))\n",
    "\n",
    "            for dx, dy in dirs:\n",
    "                nx, ny = x+dx, y+dy\n",
    "                if nx < M and ny < N and board[nx][ny] == 'X':\n",
    "                    DFS(nx, ny)\n",
    "                    break\n",
    "\n",
    "        M, N = len(board), len(board[0])\n",
    "        dirs = [(1, 0), (0, 1)]\n",
    "        visited = set()\n",
    "        res = 0\n",
    "\n",
    "        for x in range(M):\n",
    "            for y in range(N):\n",
    "                if board[x][y] == 'X' and (x, y) not in visited:\n",
    "                    res += 1    \n",
    "                    DFS(x, y)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "\n",
    "        def DFS(x, y) -> None:\n",
    "            visited.add((x, y))\n",
    "\n",
    "            for dx, dy in dirs:\n",
    "                nx, ny = x+dx, y+dy\n",
    "                if nx < M and ny < N and board[nx][ny] == 'X':\n",
    "                    DFS(nx, ny)\n",
    "                    break\n",
    "\n",
    "        M, N = len(board), len(board[0])\n",
    "        dirs = [(1, 0), (0, 1)]\n",
    "        visited = set()\n",
    "        res = 0\n",
    "\n",
    "        for x in range(M):\n",
    "            for y in range(N):\n",
    "                if board[x][y] == 'X' and (x, y) not in visited:\n",
    "                    res += 1    \n",
    "                    DFS(x, y)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countBattleships(self, board: List[List[str]]) -> int:\n",
    "\n",
    "        def DFS(x, y) -> None:\n",
    "            visited.add((x, y))\n",
    "\n",
    "            for dx, dy in dirs:\n",
    "                nx, ny = x+dx, y+dy\n",
    "                if nx < M and ny < N and board[nx][ny] == 'X':\n",
    "                    DFS(nx, ny)\n",
    "\n",
    "        M, N = len(board), len(board[0])\n",
    "        dirs = [(1, 0), (0, 1)]\n",
    "        visited = set()\n",
    "        res = 0\n",
    "\n",
    "        for x in range(M):\n",
    "            for y in range(N):\n",
    "                if board[x][y] == 'X' and (x, y) not in visited:\n",
    "                    res += 1    \n",
    "                    DFS(x, y)\n",
    "        return res\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
